/**
 * 
 */
package leetCode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * @author zhong
 *
 */
public class MinimumAreaRectangle {
	public int minAreaRect(int[][] points) {
		HashMap<Integer, Set<Integer>> xPoints = new HashMap<>();
		HashMap<Integer, Set<Integer>> yPoints = new HashMap<>();
		for (int[] point : points) {
			putOrCreate(xPoints, point, true);
			putOrCreate(yPoints, point, false);
		}
		int minArea = Integer.MAX_VALUE;
		minArea = getFromAxas(minArea, xPoints);
		minArea = getFromAxas(minArea, yPoints);
		return minArea == Integer.MAX_VALUE ? 0 : minArea;
	}

	private int getFromAxas(int minArea, HashMap<Integer, Set<Integer>> xPoints) {
		Integer[] xList = xPoints.keySet().toArray(new Integer[0]);
		for (int i = 0; i < xList.length; i++) {
			Set<Integer> iPoints = xPoints.get(xList[i]);
			if (iPoints.size() < 2) {
				continue;
			}
			for (int j = i + 1; j < xList.length; j++) {
				Set<Integer> jPoints = xPoints.get(xList[j]);
				if (jPoints.size() < 2) {
					continue;
				}
				int area = getMinArea(iPoints, jPoints, Math.abs(xList[i] - xList[j]));
				if (area < minArea) {
					minArea = area;
				}
			}
		}
		return minArea;
	}

	private int getMinArea(Set<Integer> iPoints, Set<Integer> jPoints, int abs) {
		// 求两个交集
		Set<Integer> intersetcs = new HashSet<>(iPoints);
		intersetcs.retainAll(jPoints);
		if (intersetcs.size() < 2) {
			return Integer.MAX_VALUE;
		}
		Integer[] integers = intersetcs.toArray(new Integer[0]);
		Arrays.sort(integers);
		int minDistance = Integer.MAX_VALUE;
		for (int i = 0; i < integers.length - 1; i++) {
			int dist = integers[i + 1] - integers[i];
			if (minDistance > dist) {
				minDistance = dist;
			}
		}
		return minDistance * abs;
	}

	private void putOrCreate(HashMap<Integer, Set<Integer>> xPoints, int[] point, boolean isX) {
		int key = isX ? point[0] : point[1];
		int val = isX ? point[1] : point[0];
		if (xPoints.containsKey(key)) {
			xPoints.get(key).add(val);
		} else {
			Set<Integer> list = new HashSet<>();
			list.add(val);
			xPoints.put(key, list);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] input = { { 3, 2 }, { 0, 0 }, { 3, 3 }, { 3, 4 }, { 4, 4 }, { 2, 1 }, { 4, 3 }, { 1, 0 }, { 4, 1 },
				{ 0, 2 } };
		System.out.println(new MinimumAreaRectangle().minAreaRect(input));
	}

}
